#include "headfiles.h"

using namespace std;

int getMax(int *arr, int n) {
    int i;
    int max_val = arr[0];
    for (i = 1; i < n; i++) {
        if (max_val < arr[i]) {
            max_val = arr[i];
        }
    }

    return max_val;
}

void sortDigit(int *arr, int exp, int n) {
    int count[10] = {0};
    int *output = new int[n];
    if (output == NULL) {
        assert(false && "Allocate output error!");
        return;
    }

    int i;
    for (i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++;
    }

    for (i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (i = n - 1; i >= 0; i--) {
        output[count[(arr[i]/exp)%10] - 1] = arr[i];
        count[(arr[i]/exp)%10]--;
    }

    for (i = 0; i < n; i++) {
        arr[i] = output[i];
    }

    delete output;
}

void RadixSort(int *array, int n) {
    if (array == NULL ||
        n <= 0) {
        cout << "Invalid input!" << endl;
        return;
    }

    int max_val = getMax(array, n);
    int exp;
    for (exp = 1; max_val / exp > 0; exp *= 10) {
        sortDigit(array, exp, n);
    }

    return;
}

